// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A singly-linked list entry.
#[derive(Debug)]
pub struct SListEntry<T> {
    data: T,
    next: Option<Box<SListEntry<T>>>,
}

/// A singly-linked list.
#[derive(Debug)]
pub struct SList<T> {
    head: Option<Box<SListEntry<T>>>,
}

impl<T> SList<T> {
    /// Creates a new, empty singly-linked list.
    pub fn new() -> Self {
        SList { head: None }
    }

    /// Frees the entire list.
    pub fn free(&mut self) {
        self.head = None;
    }

    /// Prepends a new entry to the beginning of the list.
    pub fn prepend(&mut self, data: T) {
        let new_entry = Box::new(SListEntry {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_entry);
    }

    /// Appends a new entry to the end of the list.
    pub fn append(&mut self, data: T) {
        let new_entry = Box::new(SListEntry { data, next: None });
        if let Some(ref mut head) = self.head {
            let mut current = head;
            while let Some(ref mut next) = current.next {
                current = next;
            }
            current.next = Some(new_entry);
        } else {
            self.head = Some(new_entry);
        }
    }

    /// Returns the data of the given list entry.
    pub fn data(&self, entry: &SListEntry<T>) -> &T {
        &entry.data
    }

    /// Sets the data of the given list entry.
    pub fn set_data(&mut self, entry: &mut SListEntry<T>, data: T) {
        entry.data = data;
    }

    /// Returns the next entry in the list.
    pub fn next(&self, entry: &SListEntry<T>) -> Option<&Box<SListEntry<T>>> {
        entry.next.as_ref()
    }

    /// Returns the nth entry in the list.
    pub fn nth_entry(&self, n: usize) -> Option<&Box<SListEntry<T>>> {
        let mut current = self.head.as_ref();
        for _ in 0..n {
            current = current?.next.as_ref();
        }
        current
    }

    /// Returns the data of the nth entry in the list.
    pub fn nth_data(&self, n: usize) -> Option<&T> {
        self.nth_entry(n).map(|entry| &entry.data)
    }

    /// Returns the length of the list.
    pub fn length(&self) -> usize {
        let mut count = 0;
        let mut current = self.head.as_ref();
        while let Some(entry) = current {
            count += 1;
            current = entry.next.as_ref();
        }
        count
    }

    /// Converts the list to an array.
    pub fn to_array(&self) -> Vec<&T> {
        let mut array = Vec::new();
        let mut current = self.head.as_ref();
        while let Some(entry) = current {
            array.push(&entry.data);
            current = entry.next.as_ref();
        }
        array
    }

    /// Removes the given entry from the list.
    pub fn remove_entry(&mut self, entry: &mut SListEntry<T>) -> bool {
        if let Some(ref mut head) = self.head {
            if std::ptr::eq(head, entry) {
                self.head = head.next.take();
                return true;
            }
            let mut current = head;
            while let Some(ref mut next) = current.next {
                if std::ptr::eq(next, entry) {
                    current.next = next.next.take();
                    return true;
                }
                current = next;
            }
        }
        false
    }

    /// Removes entries from the list based on a callback function.
    pub fn remove_data<F>(&mut self, callback: F, data: &T) -> usize
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut removed = 0;
        let mut current = &mut self.head;
        while let Some(ref mut entry) = current {
            if callback(&entry.data, data) {
                *current = entry.next.take();
                removed += 1;
            } else {
                current = &mut entry.next;
            }
        }
        removed
    }

    /// Sorts the list using the given comparison function.
    pub fn sort<F>(&mut self, compare_func: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        let mut array = self.to_array();
        array.sort_by(|a, b| compare_func(a, b));
        self.head = None;
        for data in array {
            self.append(data.clone());
        }
    }

    /// Finds an entry in the list based on a callback function.
    pub fn find_data<F>(&self, callback: F, data: &T) -> Option<&SListEntry<T>>
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut current = self.head.as_ref();
        while let Some(entry) = current {
            if callback(&entry.data, data) {
                return Some(entry);
            }
            current = entry.next.as_ref();
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_prepend_and_append() {
        let mut list = SList::new();
        list.prepend(1);
        list.append(2);
        list.prepend(0);
        assert_eq!(list.length(), 3);
        assert_eq!(list.nth_data(0), Some(&0));
        assert_eq!(list.nth_data(1), Some(&1));
        assert_eq!(list.nth_data(2), Some(&2));
    }

    #[test]
    fn test_remove_entry() {
        let mut list = SList::new();
        list.prepend(1);
        list.prepend(2);
        list.prepend(3);
        let entry = list.nth_entry(1).unwrap();
        list.remove_entry(entry);
        assert_eq!(list.length(), 2);
        assert_eq!(list.nth_data(0), Some(&3));
        assert_eq!(list.nth_data(1), Some(&1));
    }

    #[test]
    fn test_remove_data() {
        let mut list = SList::new();
        list.prepend(1);
        list.prepend(2);
        list.prepend(3);
        let removed = list.remove_data(|a, b| a == b, &2);
        assert_eq!(removed, 1);
        assert_eq!(list.length(), 2);
        assert_eq!(list.nth_data(0), Some(&3));
        assert_eq!(list.nth_data(1), Some(&1));
    }

    #[test]
    fn test_sort() {
        let mut list = SList::new();
        list.prepend(3);
        list.prepend(1);
        list.prepend(2);
        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.nth_data(0), Some(&1));
        assert_eq!(list.nth_data(1), Some(&2));
        assert_eq!(list.nth_data(2), Some(&3));
    }

    #[test]
    fn test_find_data() {
        let mut list = SList::new();
        list.prepend(1);
        list.prepend(2);
        list.prepend(3);
        let entry = list.find_data(|a, b| a == b, &2).unwrap();
        assert_eq!(list.data(entry), &2);
    }
}
